package cn.djb.day15;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一棵二叉搜索树，请找出其中第 k 大的节点的值。
 */

class Solution_3 {

    List<Integer> list;

    public int kthLargest(TreeNode root, int k) {
        if (root == null) return 0;
        this.list = new ArrayList<>();
        dfs(root);
        return this.list.get(list.size() - k);

    }

    /**
     * 中序遍历
     *
     * @param cur
     * @return
     */
    private void dfs(TreeNode cur) {
        if (cur == null) return;
        dfs(cur.left); //左
        //中
        list.add(cur.val);

        dfs(cur.right);//右

    }

    /*-------方法2:中序遍历倒叙打印---------------*/
    int k,res;

    public int kthLargest2(TreeNode root, int k) {
        if (root == null) return 0;
        this.k = k;
        dfs(root);
        return this.res;

    }

    /**
     * 中序遍历倒叙打印
     *
     * @param cur
     * @return
     */
    private void dfs3(TreeNode cur) {
        if (cur == null) return;

        dfs(cur.right);//右
        //中
        k--;
        if (k==0){
            this.res = cur.val;
            return;
        }


        dfs(cur.left); //左

    }



    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

}